package com.leetcode.algorithm.y22.m07;

import java.util.Arrays;

/**
 * 36. 有效的数独
 * 
 * https://leetcode.cn/problems/valid-sudoku/
 * 
 * @author jie.deng
 *
 */
class Question0036Solution01 {

	public boolean isValidSudoku(char[][] board) {
		// 1-9仅出现1次
		int[] tmplArr = new int[9];
		Arrays.fill(tmplArr, 1);

		return isRowValidSudoku(board, tmplArr) 
				&& isColValidSudoku(board, tmplArr)
				&& isBlockValidSudoku(board, tmplArr);
	}

	private boolean isBlockValidSudoku(char[][] board, int[] tmplArr) {
		for (int block = 0; block < 9; block++) {
			int[] cntArr = Arrays.copyOf(tmplArr, 9);
			for (int i = 0; i < 3; i++) {
				int row = i + block / 3 * 3;
				for (int j = 0; j < 3; j++) {
					int col = j + block % 3 * 3;
					if (board[row][col] != '.') {
						if (cntArr[board[row][col] - '1'] == 0) {
							return false;
						}
						cntArr[board[row][col] - '1']--;
					}
				}
			}
		}
		return true;
	}

	private boolean isColValidSudoku(char[][] board, int[] tmplArr) {
		for (int col = 0; col < 9; col++) {
			int[] cntArr = Arrays.copyOf(tmplArr, 9);
			for (int row = 0; row < 9; row++) {
				if (board[row][col] != '.') {
					if (cntArr[board[row][col] - '1'] == 0) {
						return false;
					}
					cntArr[board[row][col] - '1']--;
				}
			}
		}
		return true;
	}

	private boolean isRowValidSudoku(char[][] board, int[] tmplArr) {
		for (int row = 0; row < 9; row++) {
			int[] cntArr = Arrays.copyOf(tmplArr, 9);
			for (int col = 0; col < 9; col++) {
				if (board[row][col] != '.') {
					if (cntArr[board[row][col] - '1'] == 0) {
						return false;
					}
					cntArr[board[row][col] - '1']--;
				}
			}
		}
		return true;
	}

}